package dp.minCostClimbingStairs;
/**
 * @Date 2020/04/12
 * @author 王光浩
 * @Thinking 使用DP
 * 			  最优子结构：爬到第 i 层耗费的最小体力为 爬到第 i-1 层耗费体力 和 爬到第 i-2 层耗费体力的最小加上第 i 层耗费的体力
 * 			 状态转移方程： f(i)=cost[i]+min(f(i-1),f(i-2))
 */
public class MyMethodTwo {
	public int minCostClimbingStairs(int[] cost) {
		for(int i=2;i<cost.length;i++) {
			cost[i]=cost[i]+Math.min(cost[i-1], cost[i-2]);
		}
		return Math.min(cost[cost.length-1], cost[cost.length-2]);
	}
}
